/*
*
给你一个正方形字符数组 board ，你从数组最右下方的字符 'S' 出发。

你的目标是到达数组最左上角的字符 'E' ，数组剩余的部分为数字字符 1, 2, ..., 9 或者障碍 'X'。在每一步移动中，你可以向上、向左或者左上方移动，可以移动的前提是到达的格子没有障碍。

一条路径的 「得分」 定义为：路径上所有数字的和。

请你返回一个列表，包含两个整数：第一个整数是 「得分」 的最大值，第二个整数是得到最大得分的方案数，请把结果对 10^9 + 7 取余。

如果没有任何路径可以到达终点，请返回 [0, 0] 。

示例 1：

输入：board = ["E23","2X2","12S"]
输出：[7,1]
示例 2：

输入：board = ["E12","1X1","21S"]
输出：[4,2]
示例 3：

输入：board = ["E11","XXX","11S"]
输出：[0,0]

提示：

2 <= board.length == board[i].length <= 100

  - @author ala
  - @date 2024-09-20 09:20
*/
package main

import "fmt"

func main() {
	//board := []string{"E23", "2X2", "12S"}
	//board := []string{"E12", "1X1", "21S"}
	//board := []string{"E11", "XXX", "11S"}
	//board := []string{"E489316X53677838369158826X58629X9X9655X33126763X1577867516569451961896X485X45851X9195X95591585822X29", "X5211753853X6X24459X68156165529823565X4856449472X45X136X31674X243956883153X98256476935255X6X4839X325", "8218396X13647222795X2X781785648717539X783898288936X4982694159X452347211175124XXX5314563X334133237166", "293X693851X4555788715276468757XX64765X444487471388X4929323X84937X229341613XX57592157666135679738X277", "X628144814998948913923X4249X98713416635871683799816513X51562X1X15577913771715888X8946383114784XX9231", "15212728X659X896196856341687215634447866855X65527X58491364231755211X3955759352911959989143X9X43XX858", "698287181793848756688585X5595847622538878188131393X1342893X17X581X196662595184X419273227X6894977X711", "682151X7247415814116279X7X41889871792214636X37799125411973X69374727953X6336X93X5555X1792327416645637", "7X35455625996429X431113547X6846489644162X7621758X654774X952289247399X3X29668X432925X5656X866X974699X", "136XX9493443131X1X3921316436277983526X777185X896426589691146849X291718XX18X3618212145236X9217582X791", "173271555X7921X738586422961937398716X5381549512999246124X946X2318XX55565X76X675419672479576956176646", "224398X5X6162231165273513X72943734889283X89927264945865X71138617976X44X69642735X1341X997X856129621X7", "36919XX2474962271XX412794259413731215967X11316133998776638834971973X22659779X2783X2X1613339X661X2445", "84686X3346X486622551876X791X7353753684484525X5197753X438412265138994585X48X3X4579173697652854213378X", "883689833866733272561X87X322671572396X48X86881719473164X3661899123449865584271X4334X5614146589325237", "57X87615275447XX6884591126263X62673678558931X25717526452297282464XX25259183X7248643127X6527491595424", "X633153247365X3732X911X71165X96382435X1582559373568X114537269138X969942781X986769XX8311X9955X7782434", "6775111422X76898X9495X5X3237797XX219277X19785249X462589XX1X1416275995957235876X9651352X8551595447931", "78613X2X79648X4814X88673371295382439134957X8871842X99162628694X64181267497X66X2149X99314832615592712", "94335X47235451257821375643717X6582X486X116X5117949193194858946X4338991331X739784X32283121X582295384X", "7646777932865164732X8356222X728X6619X8883326852454X79584999X1191959886285819638981618284972858137673", "6X8X1842851911959818X5X7427581288921754455X1X9533X29167315X4382717562723852114833X1769222X7X53142976", "2642144669X19613836214431234925X63984228661X196859X363396193144472826X823594X67381968X47799236261765", "386224X63412X2262424936437156917X73273372196X84421528516279625815338379X126858836968224X865X5774617X", "615988233973917881X77343166242772388875973479599X51X53796437817X43952988X1213728X4788253683XX69569X8", "25X54533XX143257X783591694748278897772655X2673366479839925956198322874468819759236X82749363X9948X584", "X61X325871583275X2934X16X5686167267547384267843799X973939X65839818679973375493715X591968231851X81387", "8X24747X57154X46441326222379998X8777325683X545X28155886134423299986X66295X916987659X488199X322X22382", "26484X1235667318X9786525587943X14689353712476897X4X78687X8341252688964759179X3437534821488485X88767X", "93X24XX59366742987338X43199573583126754835719735119117733198782X78363469X9X78989X3485792739848133621", "56297846874886X81336346177X1158X9813X5742XX1X276237XX5X5119529184193516554X446792X99648531511X369653", "1731X35X6525665611535976762X93549296758256638X24231984X646XX115317284973X1XX2926889X138793XX73X3X517", "648771359334X76717124X258466435777398268172667158X187373X291957662256X212812379526329119X74253748X92", "435488X953618194353485757729149X911511681968891315934X735X95X575X741776841X81671261X5481276288713X47", "521258687X893172873XX1198332398X494X2347774X2567939582968194723352682X5773399X621X949133X2X268463164", "2943973X3X329934518897124964X21199X272396218876193797818687517535XX81939892333697722262924X264868562", "775831621758389381X12943744475968717782XX5188236X5927424819X6X22786X83384543147985X53X9X41632961X639", "68731439374124243219X217419X458675532266695X1587X689X6964719495XX518X47XX61511143X3966889XXX81251975", "13334999385589515565112935155532165568452767797X4975863835461X5X6832263845981511X17511X46184659X8493", "37914X918579156879X6983XX536X211X8237429X424X96439581921493X72596339X181611X68515X59512555324X827485", "XX2916882X28384357X5X98X975X321X5X1187477838657X3348297576243354267999959988277X784X4431872178698199", "91X441X444325993943776948895481696441867181558964739363776286349X3236174172495X857898371X3489181X797", "27759245X311986X8413714X1X1X24468177643676363135127619582X3X34356343X4X7XX335514X3355171217434136231", "2336361X1789587341411174823828XX28241851659X4496X413295X3113X8X3936XX4715222634217975772766974514X11", "251451888215X97669496793538156667854X7X83792X53384426X9X5X749447894957151617X3285X87159228666833X413", "1X561843X7638217567265565854826X96636X22847662543734267575XX8646488294728829198353488829886188571778", "1X563X995229164X576761419X57X496768523768282X96895162299184759X38324291933X6141427543422881962934511", "8885112224X686899326X63132X1332339831782199X13341X37724351652X16548X617594162438X14285431915859X7691", "2119111346132X921868X284515578825X143X9757X74X82X77261378975561412811427442519X1462714581349X7246455", "129844523X77772452X28562434X1945X39593657X7X7599X217883127175844918X3XX2897X14X245836X64X4X991274561", "5948288X57427633593215247571342878243949732X1395X12XXX984X9228592715347367519X99644466X852X839936169", "94993798376846756855X9X549846813533239249673623X9472229564637191487X6719X6746625289894X65884421373X8", "936467X73997455X317415795X68275214635674127355815X7413841613174925554173XX24711689X72X1865527637X18X", "3728X86265467784848751335875978518765761497826129196982X8571233856569X14X871X3374984846151854875X614", "53X3188131827446872943889X55585881X846327X6X588944835924391998X564259251X2583X325213X52391247453X233", "961X586XX3879X4X2678914281844386276347471759151573734172686139365X86279242482165X478X3X2235448258X1X", "33333455755423949373694X831X5667687237434275732X3747511499945975569X32863441X33471544345X886X23844X9", "37292632X183349211678755XX766X84795334662697719373811217732XX5XX165918936291521888237X2277537X36X784", "242419556X59668822481616329X146496X9X8X78262473346XX3617187694X39X18563X2538635675926361857178871264", "8271367116391212694437923331756826468492486965669734886736X633279276924193862541X1962987X4442622X492", "7594362739329946514697X2241242132275349X4664X141192641528563289XX26123862941X985497438XX6447X4854229", "XX586546861X5286732539793581691961778728761751451845992371951847483949558972822819925968X1428284172X", "8X126456X865X745756X9X54149XX15664X3X371172658678996221197117X22744253441744X2745X786414872739X26216", "217815665537X21984522453895516X11267377X46525155898X656X951351X56625187X82488451247X66594X696X4X25X9", "75277313X2367X482928X21XX955433332355X39952X9625643X56143786399474994XX73152X82321671124977X52865339", "96384X66441945X68729968258865416872X484395733474292151933324X72878948386878X387135121173212517818624", "68X9X95833576199X23X46526641686X6X18655915425557951732XX4X272X5687X4X33962X44294823686679783X7948111", "2X433191574449717X13196X1481X899X679763X33X173311826155X56612841638X44389X556X642267794818516539793X", "X84465779725286XX86478X127282882175X223X21924438X953182618342X8781458755413XXX42727222X1321344598X46", "3452X82X8552X249441693492X21X7463321479167713487951X129X8X87X197597658389X85122231768584714419124X63", "797874563733887X21981795527768519X78285595256X335123X59181598X31635195664777963212831925331461475129", "5159X953359299X157249192X7632X182299825754427X53183X1179824671826X913637832X5586881X325594656X579953", "512912X64237693291454716X651X336391979449427X67495X7438544441558595188286218937XX293X498729X32917146", "5667612264886688966261X43X255156211254218X12392118X3258658319438664815X55749818633347555984437X26396", "64X64113381162137X3246685936329X65424254296621687442669X1X614559111845685X136X59893X727867X412788397", "7X31811XX823586X72591X96458X4777259585X192831X7X49X2182X18354385XX5547171X6565392218X47297948434X597", "9X2287145497151X5X4935X736627757X89795592X8747X73623X65918951314348651X327X62X1518386363992746624237", "699142X76617536647823735298235841658X53911856417875523497412125641923425533934135621176382492397757X", "965524935112995433873964648995194628326XXX53156359244859755556173834385979661519X62376936947452X68X6", "257X48938579942813XX3115873X211165586X674X5774498368169286654784242815714967X72323548782XX8151915137", "34X5823XX4949X513333511417268163577615268542496X8986777X3846X828658899663411259776619861795398143581", "743921X5641293258896542X16965858563819212657567X3232865X724X5112982469982124242X97918669363698456947", "478467X641221X9X34826X5972X58643X4X8857XX5944X652446471X93257951114961793664X74385X81X61559246645X61", "443418982X113X16147X7274526731439965X29254284578482948X2626726X739554586777299414X48396819946864X565", "675131352846254X3325X98223X55963337X6514827762999781944X93X4X838578844763481353331X71685133621768528", "3391X3181941XX5X483X9149642816XX774XX2199X999692593944443752315369643442881X714958425337534767841395", "39128922724X1574X13581X967X51988285925322993X5X68624261489485271617328246X23333822112X864138X4913751", "68462434X48777931174X168X66332646X7459788862X5634845915399248X41779429727395143875772997933586893494", "42291X2949121592862568486291761X75576456194199X41311246X61X9593136258692X65565483X293763713637255316", "778281352136X67466685358982696754X5618XXX58669658X294985227829434591538775493X3157985455X4X998X67X7X", "7X9192X586289418893831X778937546563227266459476761234998875894X71711962X32XX169935X9527622181312X569", "23512133328X927911672512681966751158547X61851825735646X5798148X496753X3X75X6419679394X59452X78721X84", "7733943X33224784776585X2162417143X12425861517779345456394816598X5XXX9X85X9X1945X43459625346779567853", "X262452X159X1741524X859642412194732292656954X96X3X16445531539X54736X73586424966736X37742739X152X5358", "2X19878696293614X1X67173647478672762415875X648845X573216998X914987X24696219414588483688987X474552X72", "397986345X2X4768378574717177534876369131X19688736766893531852325353337X9716561X4X6XX48782562675566X1", "X31921759556X475X9X873671761633666486718419439X1X911X38237852291534238X5781761875185185X565488913861", "32477544363234589744717XX7639X8244991379445X5X4449X976157196987586275551561192141846X3966758465X39XX", "5X536353292273X67992X1368129871397X946X76X95973115675419298311745737998X537182171X177226361561X555X9", "582X137X78196669824158545243984762986962598X97X4296748677549X39X882679175781871X1554332318323737719S"}
	board := []string{"E999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999S"}

	fmt.Println(pathsWithMaxScore(board))
}

func pathsWithMaxScore(board []string) []int {
	M, N = len(board), len(board[0])
	grid := toGrid(board)

	return maxValAndPathCount(grid)
}

var MOD int = 1e9 + 7
var M, N int

func toGrid(board []string) [][]int {
	grid := make([][]int, M)
	for i := 0; i < M; i++ {
		grid[i] = make([]int, N)

		for j := range board[i] {
			c := board[i][j]
			if c == 'X' {
				grid[i][j] = -1
			} else {
				grid[i][j] = (int)(c - '0')
			}
		}
	}
	grid[0][0], grid[M-1][N-1] = 0, 0
	return grid
}
func maxValAndPathCount(grid [][]int) []int {
	dp, ps := make([][]int, M), make([][]int, M)
	for i := range dp {
		dp[i], ps[i] = make([]int, N), make([]int, N)
	}
	//	从左上到右下，从右下到左上，是一样一样的
	//	dp[i][j] = max(左, 左上, 上) + grid[i][j]
	for i := 0; i < M; i++ {
		for j := 0; j < N; j++ {
			if i == 0 && j == 0 {
				dp[i][j], ps[i][j] = 0, 1
				continue
			}

			v := grid[i][j]
			if v == -1 {
				dp[i][j], ps[i][j] = -1, 0
				continue
			}

			left := -1
			if j > 0 {
				left = dp[i][j-1]
			}
			leftTop := -1
			if j > 0 && i > 0 {
				leftTop = dp[i-1][j-1]
			}
			top := -1
			if i > 0 {
				top = dp[i-1][j]
			}
			_v := max(left, leftTop, top)
			dp[i][j] = choose(_v != -1, max(left, leftTop, top)+v, -1)

			if _v == left && j > 0 {
				ps[i][j] = (ps[i][j] + ps[i][j-1]) % MOD
			}
			if _v == leftTop && i > 0 && j > 0 {
				ps[i][j] = (ps[i][j] + ps[i-1][j-1]) % MOD
			}
			if _v == top && i > 0 {
				ps[i][j] = (ps[i][j] + ps[i-1][j]) % MOD
			}
		}
	}

	if dp[M-1][N-1] == -1 {
		return []int{0, 0}
	}
	return []int{dp[M-1][N-1], ps[M-1][N-1] % MOD}
}

/**
 *	三目运算符
 */
func choose(eva bool, a, b int) int {
	if eva {
		return a
	} else {
		return b
	}
}
